package week;


import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-08 22:18
 **/
public class Week2 {

    public int minimumOperations(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        Map<Integer, Integer> ji = new HashMap<>();
        Map<Integer, Integer> ou = new HashMap<>();
        for (int i = 0; i < n; i += 2) {
            ji.put(nums[i], ji.getOrDefault(nums[i], 0) + 1);
        }

        for (int j = 1; j < n; j += 2) {
            ou.put(nums[j], ou.getOrDefault(nums[j], 0) + 1);
        }

        PriorityQueue<int[]> pq1 = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        PriorityQueue<int[]> pq2 = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : ji.entrySet()) {
            pq1.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        for (Map.Entry<Integer, Integer> entry : ou.entrySet()) {
            pq2.offer(new int[]{entry.getKey(), entry.getValue()});
        }

        int[] arr1 = pq1.poll();
        int[] arr2 = pq2.poll();
        if (arr1[0] != arr2[0]) {
            return n - arr1[1] - arr2[1];
        }

        if (arr1[1] > arr2[1]) {
            if (pq2.isEmpty()) {
                return n - arr1[1];
            } else {
                arr2 = pq2.poll();
                return n - arr1[1] - arr2[1];
            }
        }

        if (arr1[1] == arr2[1]) {
            int t = arr1[1];
            if (pq1.isEmpty() && pq2.isEmpty()) {
                return n - t;
            }

            if (pq1.isEmpty()) {
                arr2 = pq2.poll();
                return n - t - arr2[1];
            }

            if (pq2.isEmpty()) {
                arr1 = pq1.poll();
                return n - t - arr1[1];
            }

            arr1 = pq1.poll();
            arr2 = pq2.poll();
            return n - t - Math.max(arr1[1], arr2[1]);
        }

        if (pq1.isEmpty()) {
            return n - arr2[1];
        }

        arr1 = pq1.poll();
        return n - arr1[1] - arr2[1];
    }

    public long smallestNumber(long num) {
        if (num == 0) {
            return 0;
        }

        //flag: 是否为负数
        boolean flag = false;
        if (num < 0) {
            flag = true;
        }

        List<Integer> list = new ArrayList<>();
        long res = 0;
        if (flag) {
            num = -num;
            while (num != 0) {
                list.add((int) (num % 10));
                num /= 10;
            }
            list.sort((a, b) ->  b - a);
            int size = list.size();
            for (int a : list) {
                res = res * 10 + a;
            }
        } else {
            while (num != 0) {
                list.add((int) (num % 10));
                num /= 10;
            }
            Collections.sort(list);
            int zeroN = 0;
            while (list.get(zeroN) == 0) {
                ++zeroN;
            }
            res = list.get(zeroN);
            for (int i = 0; i < zeroN; i++) {
                res = res * 10;
            }
            for (int i = zeroN + 1; i < list.size(); ++i) {
                res = res * 10 + list.get(i);
            }
        }

        return flag ? -res : res;
    }

    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        int[] res = new int[nums.length];
        for (int num : nums) {
            if (num < pivot) {
                list1.add(num);
            } else if (num == pivot) {
                list2.add(num);
            } else {
                list3.add(num);
            }
        }

        int i = 0;
        for (int num : list1) {
            res[i++] = num;
        }

        for (int num : list2) {
            res[i++] = num;
        }

        for (int num : list3) {
            res[i++] = num;
        }
        return res;
    }

    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            left[i] = nums[i - 1] == 0 ? left[i - 1] + 1 : left[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            right[i] = nums[i] == 1 ? right[i + 1] + 1 : right[i + 1];
        }

        int max = 0;
        for (int i = 0; i <= n; i++) {
            max = Math.max(max, left[i] + right[i]);
        }

        for (int i = 0; i <= n; i++) {
            if (left[i] + right[i] == max) {
                list.add(i);
            }
        }
        return list;
    }

    /*public static int minSwaps(int[] nums) {
        int count = 0, min = 0;
        for (int num : nums) {
            count += num;
        }
        for (int i = 0; i < count; i++) {
            min += 1 - nums[i];
        }
        for (int i = 0, j = min; i < nums.length; i++) {
            min = Math.min(min, j += nums[i] - nums[(i + count) % nums.length]);
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(minSwaps(new int[]{0, 1, 0, 1, 1, 0, 0}));
        System.out.println(minSwaps(new int[]{0,1,1,1,0,0,1,1,0}));
        System.out.println(minSwaps(new int[]{1,1,0,0,1}));
        System.out.println(minSwaps(new int[]{1}));
        System.out.println(minSwaps(new int[]{1,1,1,0,0,1,0,1,1,0}));
    }*/

    class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

}
